In machine vision systems, a run-time image is often searched for a pattern in the image using a known pattern called a model, a model image, or a template. A result of such a search is called a “pose”, which is a transformation that describes the n-dimensional position of the template that provides the closest match to the pattern sought in the run-time image. Thus, the pose maps points from a template (or model, or model image) to points in a run-time image.
It is known to perform a search as a two-step process, including a coarse search, followed by a fine search, the fine search sometimes being called “pose refinement”, because the result of the coarse search is a pose. For example, pose refinement is used in PatMax™, sold by Cognex Corporation, Natick Mass. In PatMax™, an initial affine transformation, produced by a coarse search mechanism, is refined by a pose refinement mechanism so as to provide a fine search result.
Affine transformations include translation, uniform scale, and rotation. However, PatMax™ cannot effectively search for patterns that require a non-linear transformation to map from the template to the run-time image. Examples of such non-linear transformations include: thin-plate spline, cone, cylinder, perspective, and polynomial.
There are search mechanisms that can effectively search for patterns that require a non-linear transformation to map from the template to the run-time image. For example, the search mechanism disclosed in U.S. Pat. No. 7,190,834, filed Jul. 22, 2003, entitled “Methods for Finding and Characterizing a Deformed Pattern in an Image” can effectively do such searching. However, the result from such searching as disclosed therein is a coarse search result, and such coarse search results require pose refinement for many applications that require a high degree of accuracy. Consequently, there is a need for a pose refinement mechanism that can effectively refine coarse non-linear search results.
Further, it is known that pose refinement can be used to perform tracking of a pattern in an image that is undergoing transformations over a sequence of images. However, since known pose refinement mechanisms are linear, being limited to performing only affine transformations, many important transformations of patterns in a sequence of run-time images cannot be tracked. In particular, since tracking of moving three-dimensional objects involves the perspective transformation, a form of non-linear transformation, this important transformation cannot be tracked over a sequence of run-time images using known methods.